#include<iostream>
#include<vector>
#include<stack>
using namespace std;


class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        stack<pair<int, int>> stData; // temp  posi
        stack<int> retSt;
        vector<int> ans;
        ans.resize(len, 0);
        for (int i = 0; i < len; i++) {
            if (!stData.empty()) {
                pair<int, int> tmpTop = stData.top();
                while (tmpTop.first < temperatures[i] && !retSt.empty()) {
                    int digTop = retSt.top();
                    ans[tmpTop.second] = digTop;
                    retSt.pop();
                    stData.pop();
                    if (!retSt.empty()) retSt.top() += digTop;
                    if (!stData.empty()) tmpTop = stData.top();
                }
            }
            stData.push(make_pair(temperatures[i], i));
            retSt.push(1);
        }
        return ans;
    }
};